package com.ming.learn.from.carl.string;

import static com.ming.commons.utils.MyStringUtils.reverse;

/*
题目：151.翻转字符串里的单词
 */
public class Of20201227LeetCode151 {
    /*
    给定一个字符串，逐个翻转字符串中的每个单词。
    示例 1：
    输入: "the sky is blue"
    输出: "blue is sky the"
    示例 2：
    输入: "  hello world!  "
    输出: "world! hello"
    解释: 输入字符串可以在前面或者后面包含多余的空格，但是反转后的字符不能包括。
    示例 3：
    输入: "a good   example"
    输出: "example good a"
    解释: 如果两个单词间有多余的空格，将反转后单词间的空格减少到只含一个。
     */
    public static void main(String[] args) {
        System.out.println(reverseWords("  abc  bcd   haha   "));
    }

    /*
    思路:
    移除多余空格
    将整个字符串反转
    将每个单词反转
     */
    private static String removeExtraSpaces(String s) {
        char[] chars = s.toCharArray();
        int slowIndex = 0, fastIndex = 0; // 定义快指针，慢指针
        // 去掉字符串前面的空格
        while (chars.length > 0 && fastIndex < chars.length && chars[fastIndex] == ' ') {
            fastIndex++;
        }
        for (; fastIndex < chars.length; fastIndex++) {
            // 去掉字符串中间部分的冗余空格
            if (fastIndex - 1 > 0
                    && chars[fastIndex - 1] == chars[fastIndex]
                    && chars[fastIndex] == ' ') {
                continue;
            } else {
                chars[slowIndex++] = chars[fastIndex];
            }
        }
        if (slowIndex - 1 > 0 && chars[slowIndex - 1] == ' ') { // 去掉字符串末尾的空格
            return new String(chars).substring(0, slowIndex - 1); //substring 左闭右开
        } else {
            return new String(chars).substring(0, slowIndex); // 重新设置字符串大小
        }
    }

    /*
        private static String reverse(String s, int start, int end) {
            char[] chars = s.toCharArray();
            for (; start < end; start++, end--) {
                chars[start] ^= chars[end];
                chars[end] ^= chars[start];
                chars[start] ^= chars[end];
            }
            return new String(chars);
        }
     */

    private static String reverseWords(String s) {
        s = removeExtraSpaces(s); // 去掉冗余空格
        s = reverse(s, 0, s.length() - 1); // 将字符串全部反转
        int start = 0;
        for (int i = 0; i < s.length(); i++) {
            if (s.charAt(i) == ' ') {
                s = reverse(s, start, i - 1);
                start = i + 1;
            }
        }
        s = reverse(s, start, s.length() - 1);//最后一个单词
        return s;
    }
}
